普通 Map 的使用和注意事项 Go 内建的 map 类型为 map[K]V,其中,key 类型的 K 必须是可比较的(comparable),也就是可以通过 == 和 != 操作符进行比较;value 的值和类型无所谓,可以是任意的类型,或者为 nil。
在 Go 语言中,bool、整数、浮点数、复数、字符串、指针、Channel、接口都是可比较的,包含可比较元素的 struct 和数组,这俩也是可比较的,而 slice、map、函数值都是不可比较的。
注意事项一 如果使用 struct 类型做 key 其实是有坑的,因为如果 struct 的某个字段值修改了,查询 map 时无法获取它 add 进去的值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 type mapKey struct { key int } func main () { var m = make (map [mapKey]string ) var key = mapKey{10 } m[key] = "hello" fmt.Printf("m[key]=%s\n" , m[key]) key.key = 100 fmt.Printf("再次查询m[key]=%s\n" , m[key]) }
注意事项二 在 Go 中,map[key]函数返回结果可以是一个值,也可以是两个值。如果获取一个不存在的 key 对应的值时,会返回零值。为了区分真正的零值和 key 不存在这两种情况,可以根据第二个返回值来区分。
1 2 3 4 5 6 7 8 9 10 func main () { var m = make (map [string ]int ) m["a" ] = 0 fmt.Printf("a=%d; b=%d\n" , m["a" ], m["b" ]) av, aexisted := m["a" ] bv, bexisted := m["b" ] fmt.Printf("a=%d, existed: %t; b=%d, existed: %t\n" , av, aexisted, bv, bexisted) }
注意事项三 map 是无序的,所以当遍历一个 map 对象的时候,迭代的元素的顺序是不确定的,无法保证两次遍历的顺序是一样的,也不能保证和插入的顺序一致。那怎么办呢?如果我们想要按照 key 的顺序获取 map 的值,需要先取出所有的 key 进行排序,然后按照这个排序的 key 依次获取对应的值。而如果我们想要保证元素有序,比如按照元素插入的顺序进行遍历,可以使用辅助的数据结构,比如 orderedmap ,来记录插入顺序。
1 2 3 4 5 6 7 8 9 10 11 import "github.com/elliotchance/orderedmap/v2" func main () { m := orderedmap.NewOrderedMap[string , any]() m.Set("foo" , "bar" ) m.Set("qux" , 1.23 ) m.Set("123" , true ) m.Delete("qux" ) }
注意事项四 和 slice 或者 Mutex、RWmutex 等 struct 类型不同,map 对象必须在使用之前初始化 。如果不初始化就直接赋值的话,会出现 panic 异常,比如下面的例子,m 实例还没有初始化就直接进行操作会导致 panic
1 2 3 4 func main () { var m map [int ]int m[100 ] = 100 }
并且从一个 nil 的 map 对象中获取值不会 panic,而是会得到零值,所以下面的代码不会报错:
1 2 3 4 func main () { var m map [int ]int fmt.Println(m[100 ]) }
特别要注意,map 作为一个 struct 字段的时候,很容易忘记初始化
1 2 3 4 5 6 7 8 9 10 11 12 13 type Counter struct { Website string Start time.Time PageCounters map [string ]int } func main () { var c Counter c.Website = "baidu.com" c.PageCounters["/" ]++ }
注意事项五 Go 内建的 map 对象不是线程(goroutine)安全的,并发读写的时候运行时会有检查,遇到并发问题就会导致 panic。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 func main () { var m = make (map [int ]int ,10 ) go func () { for { m[1 ] = 1 } }() go func () { for { _ = m[2 ] } }() select {} }
虽然这段代码看起来是读写 goroutine 各自操作不同的元素,貌似 map 也没有扩容的问题,但是运行时检测到同时对 map 对象有并发访问,就会直接 panic。
如何实现线程安全的 Map 避免 map 并发读写 panic 的方式之一就是加锁,考虑到读写性能,可以使用读写锁提供性能。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 type RWMap struct { sync.RWMutex m map [int ]int } func NewRWMap (n int ) *RWMap { return &RWMap{ m: make (map [int ]int , n), } } func (m *RWMap) Get (k int ) (int , bool ) { m.RLock() defer m.RUnlock() v, existed := m.m[k] return v, existed } func (m *RWMap) Set (k int , v int ) { m.Lock() defer m.Unlock() m.m[k] = v } func (m *RWMap) Delete (k int ) { m.Lock() defer m.Unlock() delete (m.m, k) } func (m *RWMap) Len () int { m.RLock() defer m.RUnlock() return len (m.m) } func (m *RWMap) Each (f func (k, v int ) bool ) { m.RLock() defer m.RUnlock() for k, v := range m.m { if !f(k, v) { return } } }
更高效的并发 Map, 分片加锁 虽然使用读写锁可以提供线程安全的 map,但是在大量并发读写的情况下,锁的竞争会非常激烈。
减少锁的粒度常用的方法就是分片(Shard),将一把锁分成几把锁,每个锁控制一个分片。Go 比较知名的分片并发 map 的实现是orcaman/concurrent-map
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 var SHARD_COUNT = 32 type ConcurrentMap []*ConcurrentMapShared type ConcurrentMapShared struct { items map [string ]interface {} sync.RWMutex } func New () ConcurrentMap { m := make (ConcurrentMap, SHARD_COUNT) for i := 0 ; i < SHARD_COUNT; i++ { m[i] = &ConcurrentMapShared{items: make (map [string ]interface {})} } return m } func (m ConcurrentMap) GetShard (key string ) *ConcurrentMapShared { return m[uint (fnv32(key))%uint (SHARD_COUNT)] } func (m ConcurrentMap) Set (key string , value interface {}) { shard := m.GetShard(key) shard.Lock() shard.items[key] = value shard.Unlock() } func (m ConcurrentMap) Get (key string ) (interface {}, bool ) { shard := m.GetShard(key) shard.RLock() val, ok := shard.items[key] shard.RUnlock() return val, ok }
加锁和分片加锁这两种方案都比较常用,如果是追求更高的性能,显然是分片加锁更好,因为它可以降低锁的粒度,进而提高访问此 map 对象的吞吐。如果并发性能要求不是那么高的场景,简单加锁方式更简单。
官方提供的 sync.Map 这个 sync.Map 并不是用来替换内建的 map 类型的,它只能被应用在一些特殊的场景里。
只会增长的缓存系统中,一个 key 只写入一次而被读很多次;
多个 goroutine 为不相交的键集读、写和重写键值对。
sync.Map 的实现原理如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 type Map struct { mu Mutex read atomic.Value dirty map [interface {}]*entry misses int } type readOnly struct { m map [interface {}]*entry amended bool } var expunged = unsafe.Pointer(new (interface {}))type entry struct { p unsafe.Pointer }
Store Store 可以用来设置一个键值对,或者更新一个键值对。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 func (m *Map) Store (key, value interface {}) { read, _ := m.read.Load().(readOnly) if e, ok := read.m[key]; ok && e.tryStore(&value) { return } m.mu.Lock() read, _ = m.read.Load().(readOnly) if e, ok := read.m[key]; ok { if e.unexpungeLocked() { m.dirty[key] = e } e.storeLocked(&value) } else if e, ok := m.dirty[key]; ok { e.storeLocked(&value) } else { if !read.amended { m.dirtyLocked() m.read.Store(readOnly{m: read.m, amended: true }) } m.dirty[key] = newEntry(value) } m.mu.Unlock() }
可以看出,Store 既可以是新增元素,也可以是更新元素。如果运气好的话,更新的是已存在的未被删除的元素,直接更新即可,不会用到锁。如果运气不好,需要更新(重用)删除的对象、更新还未提升的 dirty 中的对象,或者新增加元素的时候就会使用到了锁,这个时候,性能就会下降。
所以从这一点来看,sync.Map 适合那些只会增长的缓存系统,可以进行更新,但是不要删除,并且不要频繁地增加新元素。
新加的元素需要放入到 dirty 中,如果 dirty 为 nil,那么需要从 read 字段中复制出来一个 dirty 对象:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 func (m *Map) dirtyLocked () { if m.dirty != nil { return } read, _ := m.read.Load().(readOnly) m.dirty = make (map [interface {}]*entry, len (read.m)) for k, e := range read.m { if !e.tryExpungeLocked() { m.dirty[k] = e } } }
Load 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 func (m *Map) Load (key interface {}) (value interface {}, ok bool ) { read, _ := m.read.Load().(readOnly) e, ok := read.m[key] if !ok && read.amended { m.mu.Lock() read, _ = m.read.Load().(readOnly) e, ok = read.m[key] if !ok && read.amended { e, ok = m.dirty[key] m.missLocked() } m.mu.Unlock() } if !ok { return nil , false } return e.load() }
如果幸运的话,我们从 read 中读取到了这个 key 对应的值,那么就不需要加锁了,性能会非常好。但是,如果请求的 key 不存在或者是新加的,就需要加锁从 dirty 中读取。所以,读取不存在的 key 会因为加锁而导致性能下降,读取还没有提升的新值的情况下也会因为加锁性能下降。
其中,missLocked 增加 miss 的时候,如果 miss 数等于 dirty 长度,会将 dirty 提升为 read,并将 dirty 置空。
1 2 3 4 5 6 7 8 9 func (m *Map) missLocked () { m.misses++ if m.misses < len (m.dirty) { return } m.read.Store(readOnly{m: m.dirty}) m.dirty = nil m.misses = 0 }
Delete 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 func (m *Map) LoadAndDelete (key interface {}) (value interface {}, loaded bool ) { read, _ := m.read.Load().(readOnly) e, ok := read.m[key] if !ok && read.amended { m.mu.Lock() read, _ = m.read.Load().(readOnly) e, ok = read.m[key] if !ok && read.amended { e, ok = m.dirty[key] delete (m.dirty, key) m.missLocked() } m.mu.Unlock() } if ok { return e.delete () } return nil , false } func (m *Map) Delete (key interface {}) { m.LoadAndDelete(key) } func (e *entry) delete () (value interface {}, ok bool ) { for { p := atomic.LoadPointer(&e.p) if p == nil || p == expunged { return nil , false } if atomic.CompareAndSwapPointer(&e.p, p, nil ) { return *(*interface {})(p), true } } }
如果 read 中不存在,那么就需要从 dirty 中寻找这个项目。最终,如果项目存在就删除(将它的值标记为 nil)。如果项目不为 nil 或者没有被标记为 expunged,那么还可以把它的值返回。
总结